package com.cn.codebrush.数组;

import java.util.HashSet;
import java.util.Set;

/**
 * @Author Boolean
 * @Date 2022/7/20 15:04
 * @Version 1.0
 */
public class No128最长连续序列 {
    public static void main(String[] args) {
        int[] nums = {100,4,200,1,3,2};
        System.out.println(longestConsecutive1(nums));
        /*这道题目最开始大家想的肯定是sort，然后计数计算最长序列。
        但是要求时间复杂度为：o(n)，就不能用sort了。
        一般在leetcode中，对时间复杂度有要求，就用空间来换，对空间复杂度有要求，就用时间来换。

        基于这种思路我们就想要求最长的，就是要记录下有没有相邻的元素，
        比如遍历到100这个元素，我们需要查看[99, 101]这两个元素在不在序列中，这样去更新最大长度。
        而记录元素有没有这个事我们太熟悉了，用set这种数据结构，
        而set这种数据结构是需要o(n)的空间来换取的，这就是我们刚才说的用空间来换时间。
        */

    }

    public static int longestConsecutive1(int[] nums) {
        Set<Integer> set = new HashSet();
        for(int num:nums){
            set.add(num);
        }

        int res = 0;
        for(int num:nums){
            if(set.remove(num)){
                int len = 1;
                int curNum = num;
                while(set.remove(curNum+1)){
                    curNum++;
                }
                len += curNum-num;
                curNum = num;
                while(set.remove(curNum-1)){
                    curNum--;
                }
                len += num-curNum;
                res = Math.max(res,len);
            }

        }

        return res;
    }




    /**
     * 72 / 72 个通过测试用例
     * 超出时间限制
     * @param nums
     * @return
     */
    public static int longestConsecutive(int[] nums) {
        int n = nums.length;
        if(n == 0){
            return 0;
        }
        nums = longestConsecutiveHelepr(nums,0,n-1);
        int step = 1;
        int res = 0;
        for(int i =1;i<n;i++){
            if(nums[i] == nums[i-1]+1){
                step++;
            }else {
                if(nums[i] == nums[i-1]){
                    continue;
                }else {
                    step=1;
                }
            }
            res = Math.max(res,step);
        }
        res = Math.max(res,step);
        return res;
    }

    public static int[] longestConsecutiveHelepr(int[] nums,int left,int right) {
        if(left<right){
            int index = longestConsecutiveQuickSort(nums,left,right);
            longestConsecutiveHelepr(nums,left,index-1);
            longestConsecutiveHelepr(nums,index+1,right);
        }

        return nums;
    }

    public static int longestConsecutiveQuickSort(int[] nums,int left,int right) {
        int temp = nums[left];
        while(left<right){
            while(left<right && nums[right] >= temp){
                right--;
            }
            nums[left] = nums[right];
            while(left<right && nums[left] <= temp){
                left++;
            }
            nums[right] = nums[left];
        }
        nums[left] = temp;
        return left;
    }


}
